home *** CD-ROM | disk | FTP | other *** search
/ Reverse Code Engineering RCE CD +sandman 2000 / ReverseCodeEngineeringRceCdsandman2000.iso / RCE / Ebooks / Thinking in C++ V2 / C21 / SortTest.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  2000-05-25  |  2.7 KB  |  95 lines
  1. //: C21:SortTest.cpp
  2. // From Thinking in C++, 2nd Edition
  3. // Available at http://www.BruceEckel.com
  4. // (c) Bruce Eckel 1999
  5. // Copyright notice in Copyright.txt
  6. //{L} ../C20/StreamTokenizer
  7. // Test different kinds of sorting
  8. #include "../C20/StreamTokenizer.h"
  9. #include "NString.h"
  10. #include "PrintSequence.h"
  11. #include "Generators.h"
  12. #include "../require.h"
  13. #include <algorithm>
  14. #include <fstream>
  15. #include <queue>
  16. #include <vector>
  17. #include <cctype>
  18. using namespace std;
  19.  
  20. // For sorting NStrings and ignore string case:
  21. struct NoCase {
  22.   bool operator()(
  23.     const NString& x, const NString& y) {
  24. /* Somthing's wrong with this approach but I
  25.    can't seem to see it. It would be much faster:
  26.     const string& lv = x;
  27.     const string& rv = y;
  28.     int len = min(lv.size(), rv.size());
  29.     for(int i = 0; i < len; i++)
  30.       if(tolower(lv[i]) < tolower(rv[i]))
  31.         return true;
  32.     return false;
  33.   }
  34. */
  35.     // Brute force: copy, force to lowercase:
  36.     string lv(x);
  37.     string rv(y);
  38.     lcase(lv);
  39.     lcase(rv);
  40.     return lv < rv;
  41.   }
  42.   void lcase(string& s) {
  43.     int n = s.size();
  44.     for(int i = 0; i < n; i++)
  45.       s[i] = tolower(s[i]);
  46.   }
  47. };
  48.  
  49. int main(int argc, char* argv[]) {
  50.   requireArgs(argc, 1);
  51.   ifstream in(argv[1]);
  52.   assure(in, argv[1]);
  53.   StreamTokenizer words(in);
  54.   deque<NString> nstr;
  55.   string word;
  56.   while((word = words.next()).size() != 0)
  57.     nstr.push_back(NString(word));
  58.   print(nstr);
  59.   // Create a vector from the contents of nstr:
  60.   vector<NString> v(nstr.begin(), nstr.end());
  61.   sort(v.begin(), v.end());
  62.   print(v, "sort");
  63.   // Use an additional comparator object:
  64.   sort(v.begin(), v.end(), NoCase());
  65.   print(v, "sort NoCase");
  66.   copy(nstr.begin(), nstr.end(), v.begin());
  67.   stable_sort(v.begin(), v.end());
  68.   print(v, "stable_sort");
  69.   // Use an additional comparator object:
  70.   stable_sort(v.begin(), v.end(), 
  71.     greater<NString>());
  72.   print(v, "stable_sort greater");
  73.   copy(nstr.begin(), nstr.end(), v.begin());
  74.   // Partial sorts. The additional comparator 
  75.   // versions are obvious and not shown here.
  76.   partial_sort(v.begin(), 
  77.     v.begin() + v.size()/2, v.end());
  78.   print(v, "partial_sort");
  79.   // Create a vector with a preallocated size:
  80.   vector<NString> v2(v.size()/2);
  81.   partial_sort_copy(v.begin(), v.end(), 
  82.     v2.begin(), v2.end());
  83.   print(v2, "partial_sort_copy");
  84.   // Finally, the weakest form of ordering:
  85.   vector<int> v3(20);
  86.   generate(v3.begin(), v3.end(), URandGen(50));
  87.   print(v3, "v3 before nth_element");
  88.   int n = 10;
  89.   vector<int>::iterator vit = v3.begin() + n;
  90.   nth_element(v3.begin(), vit, v3.end());
  91.   cout << "After ordering with nth = " << n
  92.     << ", nth element is " << v3[n] << endl;
  93.   print(v3, "v3 after nth_element");
  94. } ///:~
  95.